package com.wyw.leetcode.learning.simple;

import com.wyw.leetcode.simple.parent.ListNode;

/**
 * leetcode topic 203
 *  移除链表元素
 *      给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
 * @Author Mr Wu （yewen.wu.china@gmail.com）
 * @Date 2021/12/22 14:52
 */
public class Topic203 {

    public static void main(String[] args) {
        ListNode listNode1 = null;
        for(int i=7; i > 1; i--) {
            ListNode listNodeNew = new ListNode(2 * i);
            listNodeNew.next = listNode1;
            listNode1 = listNodeNew;
        }
        ListNode listNodeNew = new ListNode(10);
        listNodeNew.next = listNode1;
        listNode1= listNodeNew;


        ListNode listNode = removeElements(listNode1, 10);
        System.out.println("end" );

    }

    /**
     * 迭代
     * @param head
     * @param val
     * @return
     */
    public static ListNode removeElements(ListNode head, int val) {

        //删除值相同的头结点后，可能新的头结点也值相等，用循环解决
        while(head!=null&&head.val==val){
            head=head.next;
        }
        if(head==null)
            return head;
        ListNode prev=head;
        //确保当前结点后还有结点
        while(prev.next!=null){
            if(prev.next.val==val){
                prev.next=prev.next.next;
            }else{
                prev=prev.next;
            }
        }
        return head;

    }

    /**
     * 递归
     * @param head
     * @param val
     * @return
     */
    public static ListNode removeElements1(ListNode head, int val) {
        if(head==null)
            return null;
        head.next=removeElements(head.next,val);
        if(head.val==val){
            return head.next;
        }else{
            return head;
        }
    }

    /**
     * 添加一个虚拟头节点
     * @param head
     * @param val
     * @return
     */
    public static ListNode removeElements2(ListNode head, int val) {
        //创建一个虚拟头结点
        ListNode dummyNode=new ListNode(val-1);
        dummyNode.next=head;
        ListNode prev=dummyNode;
        //确保当前结点后还有结点
        while(prev.next!=null){
            if(prev.next.val==val){
                prev.next=prev.next.next;
            }else{
                prev=prev.next;
            }
        }
        return dummyNode.next;

    }


}

